#include <bits/stdc++.h>
using namespace std;
#include "tree.h"

int getHight(TreeNode* root) {
  if (root == nullptr) {
    return 0;
  }

  int leftHight = getHight(root->left);
  int rightHight = getHight(root->right);

  return max(leftHight, rightHight) + 1;
}

/**
 * @brief 使用自上而下的递归方式，先判断根结点是否符合条件，再判断左右子树
 *
 * @param root
 * @return true
 * @return false
 */
bool judgeBalancedTree1(TreeNode* root) {
  if (root == nullptr) {
    return true;
  }

  return abs(getHight(root->left) - getHight(root->right)) <= 1 &&
         judgeBalancedTree1(root->left) && judgeBalancedTree1(root->right);
}

int getHight2(TreeNode* root) {
  if (root == nullptr) {
    return 0;
  }

  int leftHight = getHight2(root->left);
  int rightHight = getHight2(root->right);

  if (leftHight <= -1 || rightHight <= -1 || abs(leftHight - rightHight) > 1) {
    return -1;
  } else {
    return max(leftHight, rightHight) + 1;
  }
}

/**
 * @brief 自底向上的递归
 *
 * @param root
 * @return true
 * @return false
 */
bool judgeBalancedTree2(TreeNode* root) { return getHight2(root) >= 0; }